package Sort_06;

/*
 * @Author 罗
 * @date 2020/3/16 - 4:18 下午
 *
 */



import java.util.Arrays;

public class Select_Sort_03 {


    public void test(){
        int[] array = {-1,5,2,6,1,8,12,-12,6};

        selectSort(array);

        System.out.println(Arrays.toString(array));
    }

    /**
     * 选择排序法
     * @param array
     */
    public static void selectSort(int[] array){
        /*
        * 用于记录本趟循环的最小值的下标
        * */
        int minIndex = 0;
        /*
        * 用于记录本趟的最小值
        *   也可以直接交换，而不用临时变量存储中间值
        * */
        int minValue = 0;
        /*  选择排序需要(数组大小 - 1)轮排序，
                因为选择完(数组大小 - 1)个小的数之后，最后剩下的唯一一个就是最大的数
         */
        for (int i = 0; i < array.length - 1; i++) {
            /*
            * 每一轮排序又是一个循环
            * 1.假设当前的这个数是本轮排序最小的数
            *       j=i+1,可以跳过当前这个数对自己本身的比较
            * */
            minValue = array[i];
            minIndex = i;
            for (int j = i + 1; j < array.length ; j++) {
                /*
                *
                *   2.然后和这个数之后的每个数进行比较，
                *       这个数之前的数不用比较，经过之前的排序，这个数之前的数一定比这个数的本身要小
                *   3.如果发现比当前数更小的数，就重新确定最小数，并得到下标
                *     核心：不用急着交换，下标比较完之后再交换，就只用交换一次
                * */
                if(array[j] < minValue){
//                    更新最小值数据
                    minValue = array[j];
//                    更新最小值所在的下标
                    minIndex = j;
                }
            }
            /*
            * 本趟已经找出最小值的下标
            *   接下来进行交换
            *   优化：如果最小值的下标不是本步骤比较数的本身，再交换
            *           否则，如果本轮比较的最小值就是本身，相当于自己和自己交换
            *   if(minIndex != i)
            *       但是效果重复，在int j = i + 1中的+1就相当于把本身个跳过了
            * */

                array[minIndex] = array[i];
                array[i] = minValue;

        }

    }
}
